# -*- coding: utf-8 -*-
"""
@Time ： 2022/7/26 10:51
@Auth ： Mr. William 1052949192
@Company ：特斯汀学院 @testingedu.com.cn
@Function ：排序模块（库）
模块化封装
"""
from class6.homework.decs import my_time,my_time_new


@my_time
@my_time_new('ms')
def bub_sort(height):
    """
    冒泡排序
    :param height: 待排序列表
    :return:无
    """
    # 因为列表剩最后一个元素的时候，也不用比了
    for j in range(len(height) - 1):
        # 实现第一轮：两两比较，冒出最大的
        # 因为最后一个不用比，它没有后一个了
        # 每一轮比较都有一个元素不用再比了
        for i in range(0, len(height) - 1 - j):
            # 前一个和后一个比
            if height[i] < height[i + 1]:
                height[i], height[i + 1] = height[i + 1], height[i]


@my_time_new('ms')
def select_sort(height):
    # 剩下一个元素就不用比较了
    for j in range(len(height) - 1):
        # 找到最大的，记录下标
        max_index = 0
        # 每一轮要少比一个
        for i in range(1, len(height) - j):
            # 如果当前元素比最大值大，就记录当前元素下标
            if height[i] < height[max_index]:
                max_index = i

        # print(max_index)
        # 交换到末尾
        # 最后一个元素下标也要-j
        height[max_index], height[len(height) - 1 - j] = height[len(height) - 1 - j], height[max_index]


# @my_time_new()
def quicksort(height, left, right):
    """
    快速排序的函数
    :param height: 列表
    :param left: 列表的左边
    :param right: 待排序列表的右边
    :return:
    """
    # 取最右边为基准
    base = height[right]
    # 指针初始位置
    l = left
    h = right

    while l < h:
        # 一轮交换
        # 只要l还在h的左边，就一直循环
        while l < h:
            # 从左往右找到比基准大的
            if height[l] > base:
                # 交换到h位置
                height[l], height[h] = height[h], height[l]
                h -= 1
                break
            else:
                # 如果没找到就继续找
                l += 1

        while l < h:
            # 从右往左找比基准小的
            if height[h] < base:
                # 交换到l位置
                height[l], height[h] = height[h], height[l]
                l += 1
                break
            else:
                # 如果没找到就继续找
                h -= 1

    # 递归调用直达，所有部分都只剩下一个或者0个元素
    if l-1-left > 0:
        # 对左边剩下的元素进行递归
        quicksort(height,left,l-1)

    if right - h - 1 > 0:
        # 对右边剩下的元素进行递归
        quicksort(height, h+1, right)